﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Easy_70_ClimbStairs
{
    class MainProject
    {
        static void Main(string[] args)
        {
            Console.WriteLine(climbStairs(4));
            Console.ReadKey();
        }

        /// <summary>
        /// 动态规划
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static int climbStairs(int n)
        {
            if (n == 1)
                return 1;

            if (n == 2)
                return 2;

            int x_1 = 0;
            int x_2 = 1;
            int xValue = 2;
            for (int i = 0; i < n - 2; i++)
            {
                x_1 = x_2;
                x_2 = xValue;
                xValue = x_1 + x_2;
            }

            return xValue;
        }
    }

  
}
